class Grid{
  constructor(x,y) {
    this.x = x
    this.y = y
    this.f = null
    this.g = null
    this.h = null
    this.parent = null
  }
  initGrid(parent, end) {
    this.parent = parent
    this.g = parent.g + 1
    this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y)
    this.f = this.g + this.h
  }
}

const MAZE = [
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0]
]

class AStr{
  aStarSearch(start, end) {
    let openList = []
    let closeList = []
    openList.push(start)
    while(openList.length > 0) {
      let currentGrid = this.findMinGird(openList)
      openList.splice(currentGrid, 1)
      closeList.push(currentGrid)
      let neighbors = this.findNeighbors(currentGrid, openList, closeList)
      for(let grid of neighbors) {
        grid.initGrid(currentGrid, end)
        openList.push(grid)
      }
      for(let grid of openList) {
        if(grid.x == end.x && grid.y == end.y) {
          return grid
        }
      }
    }
    return null
  }
  findMinGird(openList) {
    let tempGrid = openList[0]
    for(let grid of openList) {
      if(grid.f < tempGrid.f) {
        tempGrid = grid
      }
    }
    return tempGrid
  }
  findNeighbors(grid, openList, closeList) {
    let gridList = []
    if(this.isValidGrid(grid.x, grid.y-1, openList, closeList)) {
      gridList.push(new Grid(grid.x, grid.y - 1))
    }
    if(this.isValidGrid(grid.x, grid.y + 1, openList, closeList)) {
      gridList.push(new Grid(grid.x, grid.y + 1))
    }
    if(this.isValidGrid(grid.x-1, grid.y, openList, closeList)) {
      gridList.push(new Grid(grid.x-1, grid.y))
    }
    if(this.isValidGrid(grid.x+1, grid.y, openList, closeList)) {
      gridList.push(new Grid(grid.x+1, grid.y))
    }
    return gridList
  }
  isValidGrid(x, y, openList, closeList) {
    if(x<0 || x>=MAZE.length || y < 0 || y >= MAZE[0].length) {
      return false
    }
    if(MAZE[x][y] == 1) {
      return false
    }
    if(this.containGrid(openList, x, y)) {
      return false
    }
    if(this.containGrid(closeList, x, y)) {
      return false
    }
    return true
  }
  containGrid(grids, x, y) {
    for(let grid of grids) {
      if(grid.x == x && grid.y == y) {
        return true
      }
    }
    return false
  }
}

let astr = new AStr()
let startGrid = new Grid(2, 1)
let endGrid = new Grid(2, 5)
let resultGrid = astr.aStarSearch(startGrid, endGrid)
let path = []
while(resultGrid != null) {
  path.push(new Grid(resultGrid.x, resultGrid.y))
  resultGrid = resultGrid.parent
}
let pathStr = ''
for(let i =0; i < MAZE.length; i++) {
  for(let j = 0; j< MAZE[0].length; j++) {
    if(astr.containGrid(path, i, j)) {
      // console.log("*, ")
      pathStr += "*, "
    } else {
      // console.log(MAZE[i][j] + ', ')
      pathStr += MAZE[i][j] + ', '
    }
  }
  // console.log("\n")
  pathStr += "\n"
}

console.log(pathStr)